// 堆又称优先队列 是一种特殊的二叉树，首先堆是一个完全二叉树， 然后它的每一个节点的值都不大于其父节点，对于大顶堆来说
// 小顶堆 刚好相反 ，堆顶元素就是整个堆的最值

class Heap {
    /* 这里当然是数组建堆， 作为完全二叉树 可以利用索引找到每个节点的父节点和子节点
        索引为 n 它的父节点的索引就是(n-1)>>1    子节点的索引就是 2n+1 2n +2
        compare 函数决定这是个最大堆 还是最小堆
    */
    constructor(arr, compare = (a, b) => a - b > 0, size = 63) {
        // 初始数据建堆 是从顶部开始的， 虽然这是个金字塔 ，但是地基我们最后打
        this.data = [...arr]; // 深拷贝一下
        this.maxLen = size;
        this.compare = compare
        for (let i = 1; i < this.size; i++) {
            this.bubleUp(i)
        }

        // 这里可以用数学归纳法来验证， 向一个已经建好的堆添加新的元素 ，肯定是放在最下面，然后逐个，冒泡调整上去，这样维持了堆的性质，它仍然是一个堆，
        // 这里是先建堆的第一层 只有一个元素 ，肯定是个堆， 然后第二层依次与第一个元素冒泡，这样一个三元最小堆就完成， 下面的就一样了
        if (this.size > size) {
            /* 这种写法是直接截取金字塔的最上面几层， 没有排序达不到求最小最大k个数 */
            this.data.length = size
        }
    }
    get size() { return this.data.length }


    bubleUp(i) {
        if (i == 0) return
        // let pInd = (i- 1) >>1
        // if (this.compare(this.data[pInd], this.data[i]) ){
        //     this.swap(pInd, i)
        // }
        // this.bubleUp(pInd);
        // 迭代
        while (i) {
            let pInd = (i - 1) >> 1
            if (this.compare(this.data[pInd], this.data[i])) {
                this.swap(pInd, i)
                i = pInd
            } else {
                break
            }
        }
    }
    bubleDown(i) {
        const [l, r] = [2 * i + 1, 2 * i + 2]
        if (l >= this.size) {
            return
        }
        // 这里就是要保证i这个位置的值是三者最小 不过 右孩子不一定存在 , 先记录索引比较完成之后只交换一次即可
        /*         let min  = i
                if (this.compare(this.data[i] , this.data[l])){
                    min = l
                }
                if (r < this.size && this.compare(this.data[i] , this.data[r])){
                    min = r
                }
                if (min !== i){
                    this.swap(min,i)
                    this.bubleDown(min)
                } */

        //迭代
        let cur = i
        while (2 * cur + 1 < this.size) {
            const [l, r] = [2 * cur + 1, 2 * cur + 2]
            let min = cur
            if (l<this.size && this.compare(this.data[i], this.data[l])) {
                min = l
            }
            if (r < this.size && this.compare(this.data[i], this.data[r])) {
                min = r
            }
            if (min !== i) {
                this.swap(min, i)
                cur = min;
            } else {
                break
            }
        }

    }

    swap(a, b) {

        [this.data[a], this.data[b]] = [this.data[b], this.data[a]]
    }
    // 堆又称又称优先队列 就是因为 堆都是从底部进去 从顶部出去 就像 做蛋糕的挤奶油那样
    // 这里限制一下堆的大小就和队列差不多了  
    push(el) {
  
        this.data.push(el)
        this.bubleUp(this.size - 1)
        /* 先进来再出队 这样就不用外部判断 */
        if (this.size > this.maxLen) {
            this.pop()
        }
    }
    //  堆排序就是通过不断pop出堆的最值堆顶元素来实现的 ，pop完了之后 维持住堆的性质
    //  pop了 之后 顶部空缺 尾部来补 这样数据的变动最小
    pop() {
        if (this.size === 0) return

        const ret = this.data.shift()
       
        this.data.unshift(this.data.pop())
        this.bubleDown(0)

        return ret
    }
    get top() { return this.data[0] } // 堆顶元素就是0


}
function getRandArr(n) {
    const arr = []
    for (let i = 0; i < n; i++) {
        arr.push(Math.random() * 90 + 10 | 0);
    }
    return arr

}


class Heap2 {
    /* 默认最小堆 */
    constructor(data = [], k = 0, compare = (a, b) => a > b) {
        this.data = [];
        this.limit = k;
        this.compare = compare
        for (let i = 0; i < data.length; i++) {
            this.push(data[i])
        }
    }
    /* 建堆从最高层开始 ，从堆尾入堆， */
    bubleUp(index) {
        /* 父节点的索引为 n/2 -1 */
        let pInd = (index - 1) / 2 | 0;
        while (index) {
            if (this.comp(pInd, index)) {
                this.swap(pInd, index)
                index = pInd;
                pInd = (index - 1) / 2 | 0
            } else {
                break
            }
        }

    }
    bubleDown(index) {
        /*  先比较然后直接与最小的进行交换*/
        let left = index * 2 + 1, right = index * 2 + 2, min = index;
        while (left < this.data.length || right < this.data.length) {
            if (left < this.data.length  && this.comp(min, left)) {
                min = left
            }
            if (right < this.data.length  && this.comp(min, right)) {
                min = right
            }
            if (min !== index) {
                this.swap(min, index)
                index = min;
                left = index * 2 + 1;
                right = index * 2 + 2;
                min = index;
            } else {
                break
            }

        }

    }
    comp(a, b) {
        return this.compare(this.data[a], this.data[b])
    }
    swap(a, b) {
        let t = this.data[a];
        this.data[a] = this.data[b]
        this.data[b] = t
    }
    push(v) {

        this.data.push(v);
        this.bubleUp(this.data.length - 1)


        if (this.data.length > this.limit) {
            this.pop()

        }

    }
    pop() {
        /* 优先队列 队首出队 队尾补到队首 */
        let last = this.data.pop()
        const res = this.data[0];
        this.data[0] = last
        this.bubleDown(0)
        return res

    }
    get top() { return this.data[0] }
}



// 输出二叉树 默认数组是层序遍历完全二叉树
function logBinaryTree(arr = []) {
    let len = arr.length;
    // 计算深度从0开始  高度为depth+ 1
    let depth = 0, yushu = len
    while (yushu >= 1 << depth) {
        yushu = yushu - (1 << depth);
        depth++
    }
    let maxLen = 1 << depth;
    console.log('层数', depth);
    for (let index = 0; index <= depth; index++) {
        const l = (1 << index) - 1, r = (1 << index) + l;
        // 补位是也是翻倍 2^n -1  间距是翻倍的
        let diff = depth - index + 1, gap = (1 << diff) - 1, pre = (1 << (diff - 1)) - 1
        // console.log('间距', gap, '补位', pre, l, r);
        console.log()
        let temp = arr.slice(l, r)
        if (index) {

            console.log('  '.repeat(pre) + temp.join('  '.repeat(gap)))
        } else {
            console.log('  '.repeat(pre) + temp.join(''))
        }

    }
}


let arr1 = getRandArr(31);
// console.log(arr1);
let heap = new Heap(arr1, (a, b) => a < b, 31)
let heap2 = new Heap2(arr1, 31, (a, b) => a < b)
// let heap3 = new Heap([0,1,1,2,4,4,1,3,3,2],(a, b) => a < b, 6 )
// let heap4 = new Heap2([0,1,1,2,4,4,1,3,3,2, 8],6,(a, b) => a < b,  )
// console.log(heap4.data);
// logBinaryTree(heap.data)
const testArr =[333, 456, 308, 569, 784, 727, 361, 17, 422, 337, 826, 436, 308, 169, 174, 102, 249, 790, 107, 378, 2, 137, 709, 381, -106, -266, -799, 136, 171, 590, -96, 596, 97, 115, 412, 676, 360, 515, 33, 350, 497, 449, 114, 239, 166, 607, 105, 878, 394, 70, -201, -159, -451, 207, -305,-622, -498, -129, -446, 254, 229, 113, 36, 110, 497, 90, 885, 494, 647, 331, 410, 179, 1, 656, 870, 743, 713, 79, 658, 132, 787, 900, 322, 410, 866, 89, 696, 192, 157, 663, 289, 52, 504, 872, 216, 469, 588, 292, 491, 344, 242, 8, 222, 392, 572, 120, 879, 524, 667, 119, 402, 149, 92, 334, 296, 7, 17,-4, 20, 21, 90, 50, 26, 31, 99, 711, 215, 131, 275, 225, -378, 874, 570, 546, 432, 516, 806, 101, 429, 118, 276, 634, 559, 839, 577, 39, 980, 934, 20, 575, 499, 493, 132, 823, 270, 665, 45, 42, 70, 80, 78, 96, 75, 78, 22, 11];
// console.log(testArr.length)
// testArr.sort((a,b)=>a-b)
let heap5 = new Heap2(testArr,63, (a, b) => a < b )
// let heap5 = new Heap(testArr, (a, b) => a < b, 100 )
// let temp= [...heap5.data];temp.sort((a, b)=> b-a)
// console.log(temp.join(','))
// console.log(heap5.data.indexOf(535))
logBinaryTree(heap2.data)
